class Solution {
public:
    int maximalRectangle(vector<vector<char>>& a) {
        int n=a.size();
        int m=a[0].size();
        vector<int> h(m);       //高度数组
        //要压缩矩阵
        int MSize=0;
        for(int i=0;i<n;i++)
        {
            //以i行为底，连续区域
            for(int j=0;j<m;j++)
            {
                //如果是0，就不用算了，如果不是，就把上面的+1
                h[j]=a[i][j]=='0'?0:h[j]+1;     
            }
            //每行结束，得到一个高度数组，转换成刚刚的柱形图求最大面积
            MSize=max(MSize,largestRectangleArea(h));
        }
        return MSize;
    }
    //柱形图最大面积
    int largestRectangleArea(vector<int>& a) {
        int n=a.size();
        int left,cur;
        int r=0;        //指向栈顶元素下一位
        int st[n];      //模拟栈
        int MSize=0;    //最大面积
        for(int i=0;i<n;i++)
        {
            //出栈
            while(r>0&&a[st[r-1]]>=a[i])
            {
                cur=st[--r];
                left=r==0?-1:st[r-1];           //底部的左
                MSize=max(MSize,a[cur]*(i-left-1));//底乘高
            }
            st[r++]=i;
        }
        while(r>0)
        {
            cur=st[--r];
            left=r==0?-1:st[r-1];
            MSize=max(MSize,a[cur]*(n-left-1));//底乘高
        }
        return MSize;
    }
};